A thesis by Urban Boquist entitled “Interprocedural Register Allocation for Lazy Functional Languages”, published by Department of Computing Science, Chalmers University of Technology on Mar. 13, 1995 is incorporated by reference herein in its entirety. This thesis describes an interprocedural register allocation algorithm, which is an extended variant of Briggs' optimistic graph coloring. Boquist uses interprocedural coalescing to achieve a custom-made calling convention for each function. Moreover, Boquist adds a restricted form of live range splitting in a way that is particularly useful for call intensive languages.
In the above described thesis (see middle of page 10), Boquist mentions two different approaches to interprocedural register allocation:                program-wide register allocation, done for all variables in the program at once; and        per-procedure register allocation, using interprocedural (program-wide) information to reduce the call and return overhead.According to Boquist, a key observation for these approaches is that procedures that cannot be active at the same time can use the same registers for local variables. Therefore, if registers are allocated for one procedure at a time in a bottom-up traversal of the procedure call graph, and avoid using registers used by descendant procedures, then there is no need to save and restore registers around procedure calls.        
Boquist also states (see top of page 38) that when generating code for a function call to the function-f, assuming the actual arguments can be found in the virtual registers a1 and a2, generation of the code:                copy a2→r2        call fwhere r1 and r2 are the virtual registers in which f expects its arguments. In the same style, the first thing f will do is:        copy r1→t1        copy r2->t2where t1 and t2 are virtual registers that will be used when f needs its arguments. Boquist describes virtual registers as being registers to which values are initially assumed as being allocated (see top of page 33). Boquist also refers to virtual registers as live ranges.        
According to Boquist, introducing a lot of copies for each function call may seem strange (see middle of page 38), but allows the register allocator to have “maximal freedom” to choose the registers used to pass parameters. Boquist wants as few constraints as possible to prevent different functions and call sites from negatively interfering with each other. Boquist hopes that “coalesce” will remove most of the copy instructions. The ones that it leaves behind will actually be useful (see below).
Boquist states (see middle of page 38) that “coalesce” examines each copy instruction, checking whether or not the operands conflict with each other. If they do not, coalesce will combine with the two live ranges and delete the copy instruction. The two nodes in the interference graph will be merged into one, taking the union of all neighbors. For copy a1→r1, above, this would mean computing the argument into the correct register (targeting). For copy r1→t1 above, it would mean that f will use its argument in the register where the caller put it. The order for coalesces may be important, and for best results, “high priority” coalesces should be made before others.
Boquist further states (see bottom of page 38) that in the few cases where “coalesce” fails to delete a copy instruction, it does so because the two live ranges are in conflict. This probably indicates that the “register pressure” is so high that the copy instruction actually does something useful, i.e. turning a long-lived (hard to color) live range into two shorter live ranges. The shorter live ranges will hopefully have fewer neighbors in the interference graph and will be easier to color. This may be hard to imagine, but after “coalesce” has worked on the code for a while, values in the program that at first may not seem even remotely related, can have turned into the same live range.
See also U.S. Pat. No. 5,555,417 granted to Odnert et al. on Sep. 10, 1996 and entitled “Method and Apparatus For Compiling Computer Programs With Interprocedural Register Allocation” that is incorporated by reference herein in its entirety.
Improvements to prior art methods of interprocedural register allocation are desirable.